/**
 * 单点修改最大子段和。使用DDP。
 * 令Ui是以i结尾的最大子段和，Vi是i以内的最大子段和，定义矩阵运算：
 * | Ui |   |  Ai -inf  Ai |   | U[i-1] |
 * | Vi | = |  Ai   0   Ai | * | V[i-1] |
 * | 0  |   | -inf -inf  0 |   |   0    |
 * 
 * 使用线段树维护这个矩阵累乘积即可
 * 单点修改操作只需要把第i个位置的系数矩阵直接改就行了
 * 查询[s, e]操作需要查询[s, e]区间的矩阵积，记作M
 *              | -inf |
 *   计算出  M * | -inf | 即可得到 Vi
 *              |   0  |
 * 
 * 需要使用longlong
 * 要保证2被inf不会溢出
 * 去掉Lazy数组，否则会MLE
 * 不需要记录3*3的矩阵，只需要2*3即可，否则会MLE
 */
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;

template <typename T>
const T & mymax(const T & a, const T & b){
    return max(a, b);
}

template<typename T, typename ... Args>
const T & mymax(const T & t, const Args & ... args){
    return max(t, mymax(args ...));
}


struct SegTree{ // 线段树带延迟

using llt = long long;

int N;

struct value_type{ // 3*3的矩阵
    array<array<llt, 3>, 2> data;
    array<llt, 3> & operator [] (int p) {return data[p];}
    const array<llt, 3> & operator [] (int p) const {return data[p];}
    bool operator == (const value_type & b) const {
        for(int i=0;i<2;++i)for(int j=0;j<3;++j){
            if(data[i][j] != b[i][j]){
                return false;
            }
        }
        return true;
    }
    value_type() = default;
    value_type(const array<array<llt, 3>, 2> & b):data(b){}
    value_type(llt a):data({array<llt, 3>{a, -inf(), a}, array<llt, 3>{a, 0LL, a}}){}
};

vector<value_type> data; // 线段树

using lazy_type = llt;
vector<lazy_type> lazy; // 延迟标记

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    // assert(0);
    if(ls == value_zero()) return rs;
    if(rs == value_zero()) return ls;

    return value_type({
        array<llt, 3>{
            mymax(ls[0][0] + rs[0][0], ls[0][1] + rs[1][0], ls[0][2] - inf()),
            mymax(ls[0][0] + rs[0][1], ls[0][1] + rs[1][1], ls[0][2] - inf()),
            mymax(ls[0][0] + rs[0][2], ls[0][1] + rs[1][2], ls[0][2])
        },
        array<llt, 3>{
            mymax(ls[1][0] + rs[0][0], ls[1][1] + rs[1][0], ls[1][2] - inf()),
            mymax(ls[1][0] + rs[0][1], ls[1][1] + rs[1][1], ls[1][2] - inf()),
            mymax(ls[1][0] + rs[0][2], ls[1][1] + rs[1][2], ls[1][2])
        }
    });
}

/// 从上往下计算信息，要变动
void _dn_(int t, int s, int e, const lazy_type & delta) {
    // assert(0);
    auto & d = data[t];
    d[0][0] = d[0][2] = d[1][0] = d[1][2] = delta;
    d[0][1] = -inf();
    d[1][1] = 0;
    return;
}

/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
    // lazy.assign(n + 1 << 2, lazy_zero());
}

/// 这个函数不用动
void modify(int a, int b, const lazy_type & delta){
    _modify(1, 1, N, a, b, delta);
}

/// 这个函数不用动
value_type query(int a, int b){
    return _query(1, 1, N, a, b);
}

/// 这个函数不用动
void build(int n) {
    _build(1, 1, n);
}

/// 几乎不用动
value_type _query(int t, int s, int e, int a, int b) {
    if(a <= s and e <= b) {
        return data[t];
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    value_type ans = value_zero(); // 如果求最值，这里不能用zero
    if(a <= mid) ans = _up_(ans, _query(lson(t), s, mid, a, b));
    if(mid < b) ans = _up_(ans, _query(rson(t), mid + 1, e, a, b));
    return ans;
}

/// 几乎不用动
void _modify(int t, int s, int e, int a, int b, const lazy_type & delta) {
    if(a <= s and e <= b) {
        _dn_(t, s, e, delta);
        return;
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    if(a <= mid) _modify(lson(t), s, mid, a, b, delta);
    if(mid < b) _modify(rson(t), mid + 1, e, a, b, delta);
    _pushUp(t);
    return;
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 这个函数几乎不用动
void _pushDown(int t, int s, int e) {
    // if(lazy_zero() == lazy[t]) return;
    // auto & lz = lazy[t];
    // auto ls = lson(t), rs = rson(t);
    // int mid = (s + e) >> 1;

    // _dn_(ls, s, mid, lz);
    // _dn_(rs, mid + 1, e, lz);

    // lz = lazy_zero();
}


/// 几乎不用动
void _build(int t, int s, int e) {
    if(s == e) {
        int x; cin >> x;
        data[t] = value_type(x); // 注意提供value_type的初始化
        return; 
    }
    int mid = (s + e) >> 1;
    _build(lson(t), s, mid);
    _build(rson(t), mid + 1, e);
    _pushUp(t);
}

/// 辅助函数，视延迟的类型而变动
static const lazy_type & lazy_zero() {
    static const lazy_type LAZY0 = 0;
    return LAZY0; 
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0 = value_type({
        array<llt, 3>{0LL, 0LL, 0LL}, array<llt, 3>{0LL, 0LL, 0LL}
    });
    return VALUE0;
}

static long long inf() {
    static const long long INF = 0x8F9FAFBFCFDFEF;
    return INF;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}


};

int N, M;
SegTree St;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    cin >> N >> M;
    St.init(N);
    St.build(N);
    for(int c,a,b,q=1;q<=M;++q){
        cin >> c >> a >> b;
        if(1 == c){
            if(a > b) swap(a, b);
            auto ans = St.query(a, b);
            auto tmp = mymax(ans[1][0] - SegTree::inf(), ans[1][1] - SegTree::inf(), ans[1][2]);
            cout << tmp << "\n";
        }else{
            St.modify(a, a, b);
        }
    }
    return 0;
}